package com.hao.tree;

import com.hao.sort.QuickSort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * TODO
 *
 * @author 97472
 * @version 1.0
 * @date 2021/5/28 14:35
 */
public class HuffmanTree<E extends Comparable<E>> {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{13,7,8,3,29,6,1};
        HuffmanTree huffmanTree = parse(arr);
        System.out.println(huffmanTree);
    }

    private Node<E> root;
    // 将数组转换位霍夫曼树
    public static HuffmanTree parse(Integer[] arr){
        //将普通的数组变成节点集合
        List<Node<Integer>> arrList = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            arrList.add(new Node<Integer>(arr[i],null,null));
        }
        // 获取霍夫曼树的根节点
        Node<Integer> root = parse(arrList);
        return new HuffmanTree(root);
    }

    public HuffmanTree(Node<E> root) {
        this.root = root;
    }

    /**
     * 解析节点集合变成霍夫曼树
     * @param arr 节点的集合
     * @return
     */
    private static Node parse(List<Node<Integer>> arr){
        if (arr.size() > 1){
            // 进行排序
            Collections.sort(arr);
            // 头部的两个元素座位子节点创建一个树
            Node<Integer> childNode0 = arr.get(0);
            Node<Integer> childNode1 = arr.get(1);
            arr.remove(0);
            arr.remove(0);
            Node<Integer> parentNode;
            if (childNode0.compareTo(childNode1) > 0){
                parentNode = new Node(childNode0.value+childNode1.value, childNode0, childNode1);
            }else {
                parentNode = new Node(childNode0.value+childNode1.value, childNode1, childNode0);
            }
            //添加到原数组中
            arr.add(parentNode);
            //在进行依次解析
            return parse(arr);
        }else {
            return arr.size() == 1?arr.get(0):null;
        }
    }
    static class Node<E extends Comparable<E>> implements Comparable<Node<E>>{
        E value;
        Node<E> left;
        Node<E> right;

        public Node(E value, Node<E> left, Node<E> right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }

        @Override
        public int compareTo(Node<E> o) {
            return value.compareTo(o.value);
        }
    }

    @Override
    public String toString() {
        return "HuffmanTree{" +
                "root=" + root +
                '}';
    }
}
